The patterns, as discussed herein, are simplified forms of "regular expressions" as described in the publication entitled "Compilers: Principles, Techniques and Tools" by A. V. Aho and J. D. Ullman (Addison-Wesley, Reading, Mass. 1985). The dialing plan as employed in this specification is based on number patterns as opposed to area code and prefix maps. The pattern of the North American dial (NAD) plan is configured with a three digit area code traditionally formatted with the first digit, any number from 2 to 9 followed by a 0 or 1, and another digit from the 2 to 9 range. This is followed by seven digits with the first two constrained to 2-9 and the last five any digit.
When a given string of digits prescribes exactly to a given pattern, it is considered to "match" that pattern. For instance, 258 and 943 match the NAD pattern for the three digits following the area code, but 207 and 800 do not. When explicit digits are specified, only that explicit set is considered to match. That is, a number pattern of 123 is only matched by the number string 123.
Also, for patterns herein discussed, an "X" designates any digit, 0 through 9. Thus a pattern of 1X3 reflects any set of numbers of 103, 113, 123, through 193. Patterns may include selective digits, and brackets allow users to group selective digits into a single pattern element. The NAD area code could thus appear as [23456789][01]X. By using a hyphen, digit ranges are designated so that the area pattern becomes [2-9][01]X. Note that X is equivalent to [0-9]. Note also that a pattern of 2[013-9]2 means a pattern of 2 followed by any number except 2 followed by a 2.
A pattern is typically made up of pattern elements. A pattern element is either an explicit digit (an X) or a selective digits descriptor. Some of the common NAD patterns and their nomenclature are: 0-Operator; 911--Emergency; [2-9][2-9]XXXXX--Local Calls; and 1[2-9][01]XXXXXXXX--Long Distance Calls. To distinguish over the hyphen which is already used to designate ranges, element groups in a pattern are herein separated by a period or dot ("."). A local call pattern is represented by [2-9][2-9]X.XXXX. Accordingly, there are seventeen characters forming the pattern alphabet counting each end of the brackets and parenthesis as characters.
The final feature of patterns is the concept of fields which can vary from one digit to as many elements as form a pattern. Fields are delimited by a parenthesis. By convention, there is a default field for all numbers that are not enclosed within a parenthesis, field 0. In all other cases, fields within a number are numbered left to right beginning at one. If the pattern appears as ([2-9][2-9]X).XXXX, field one is [2-9][2-9]X and field zero is the ending XXX element.
Patterns are well suited for defining state transition tables for a fixed state machine (FSM). However, telephone systems for different applications and in different environments must comport with a variety of disciplines. The standard number patterns used in the United States, Asia and Europe all differ to one degree or another. Further, internal number patterns as with dedicated tielines, internal local network controls and the like, differ even more radically and sometimes are an adjunct to the public systems as for direct dialing of an extension which is interfaced initially via the public network number pattern.
Contemporary pattern matching involves an unacceptable degree of time complexity. That is, a character by character comparison is done against a reference pattern until a match/no match decision is made. The longer the list of patterns to compare, the more comparisons that are demanded and hence the time complexity problem. This problem is compounded where the system must handle telephone plans that have variable length prefixes. This demands a scanning of additional lists of prefixes beyond the basic pattern.
Contemporary string matching methods are efficient for small numbers of relatively small patterns such as five patterns of not more than five characters. As tables grow in size, however, the repetitive action of matching against many strings over many times grows in quadratic time. Matching by use of the present invention grows in linear time with the length of the longest, worst case pattern. This means a machine using transition and/or result tables in accordance with this invention takes exactly the same length of time for pattern recognition and response whether its transition table has one ten digit entry or a transition table with one thousand entries of ten digits each.
While tables of somewhat greater size are needed for the present invention as contrasted to string matching tables of the prior art, they still only require about 1K of data space for a reasonably complex system such as one that must recognize the general NAD plan plus eight to ten special numbers.
Some contemporary search algorithms are shown in the article by Stone et al in the June 1987 IBM Technical Disclosure Bulletin at pages 146-148, in the June 1988 IBM Technical Disclosure Bulletin article by Natarajan et al at pages 415-417, in U.S. Pat. No. 4,554,631 by Reddington, and in U.S. Pat. No. 4,580,218 by Raye. A process for constructing a search tree is described in an article by Rosenberg et al in the July 1977 IBM Technical Disclosure Bulletin at pages 846-848. Another searching technique concurrent with database update is described in U.S. Pat. No. 4,648,036 by Gallant. A discussion of pathfinding in a graph and a process for updating a searchable database on an ongoing basis are present in commonly assigned U.S. Pat. No. 4,752,890 by Natarajan and Stone.
Structures for performing parallel searches of stored data are shown in commonly assigned U.S. Pat. No. 3,195,109 by Behnke and in U.S. Pat. No. 4,595,995 by Alles. Apparatus for searching out free path routes through switching matrices in a manner useful for telephone system environments is taught in commonly assigned U.S. Pat. No. 3,511,937 by Bastian et al.
Typical contemporary telephone switching control systems limit the installation prospects because they are configured to work only with the public network environment of its installation. A PBX configured to interface with the North American dialing (NAD) plan cannot operate when attached to a non-NAD (eg: European) dialing pattern without substantial modification.